package main.java.LeetCode.ClassicalAlgorithm.KnapsackProblem.Impl;

import main.java.LeetCode.ClassicalAlgorithm.KnapsackProblem.Knapsack;

/**
 * 多限定条件背包
 */
public class MultipleKnapsack implements Knapsack {
    @Override
    public int bestChoose(int[] weights, int[] values, int cap) {
        throw new RuntimeException("该方法适用于单条件的背包");
    }

    @Override
    public int bestChooseForMultiple(int[] conditions1, int[] conditions2, int[] values, int cap1, int cap2) {
        assert conditions1.length==conditions2.length;
        assert conditions1.length==values.length;

        int[][] dp = new int[cap1+1][cap2+1];

        for(int i = 0;i<conditions1.length;i++){
            int c1 = conditions1[i];
            int c2 = conditions1[i];
            int value = values[i];

            for(int j = cap1;j>=c1;j--){
                for(int k =cap2;k>=c2;k--){
                    dp[j][k] = Math.max(dp[j][k],dp[j-c1][k-c2]+value);
                }
            }
        }
        return dp[cap1][cap2];
    }
}
